/**
 * 剑指 Offer 34. 二叉树中和为某一值的路径
 * https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/
 */
const { displayNestedArray, createTreeNode } = require('../../libs/public');

/**
 * @param {TreeNode} node
 * @param {number} rest
 * @param {number} depth
 * @return {number[][]}
 */
function dfs(node, rest, depth) {
  if (!node.left && !node.right) {
    if (rest === node.val) {
      const result = new Array(depth + 1).fill(0);
      result[depth] = node.val;
      return [result];
    }
    return null;
  }
  let result = null;
  if (node.left) {
    result = dfs(node.left, rest - node.val, depth + 1);
  }
  if (node.right) {
    const res = dfs(node.right, rest - node.val, depth + 1);
    if (res) {
      if (result) {
        // eslint-disable-next-line prefer-spread
        result.push.apply(result, res);
      } else {
        result = res;
      }
    }
  }
  if (result) {
    for (let i = 0; i < result.length; i += 1) {
      result[i][depth] = node.val;
    }
  }
  return result;
}

/**
 * @param {TreeNode} root
 * @param {number} target
 * @return {number[][]}
 */
function pathSum(root, target) {
  if (!root) {
    return [];
  }
  return dfs(root, target, 0) || [];
}

console.log(
  displayNestedArray(pathSum(createTreeNode([5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1]), 22))
  === '[[5,4,11,2],[5,8,4,5]]',
);
console.log(
  displayNestedArray(pathSum(createTreeNode([1, 2, 3]), 5))
  === '[]',
);
console.log(
  displayNestedArray(pathSum(createTreeNode([1, 2]), 0))
  === '[]',
);
